package com.xyhuo.leetcode.november;

import java.util.ArrayList;
import java.util.List;

/**
 * 三角形最小路径和
 * https://leetcode.cn/problems/triangle
 *
 * @time 2023/11/23
 */
public class MinimumTotal {

//    public static void main(String[] args) {
//        MinimumTotal minimumTotal = new MinimumTotal();
//        List<List<Integer>> triangle = new ArrayList<>();
//        List<Integer> one = new ArrayList<>();
//        List<Integer> two = new ArrayList<>();
//        List<Integer> three = new ArrayList<>();
//        List<Integer> four = new ArrayList<>();
//        one.add(2);
//
//        two.add(3);
//        two.add(4);
//
//        three.add(6);
//        three.add(5);
//        three.add(7);
//
//        four.add(4);
//        four.add(1);
//        four.add(8);
//        four.add(3);
//
//        triangle.add(one);
//        triangle.add(two);
//        triangle.add(three);
//        triangle.add(four);
//        int result = minimumTotal.minimumTotal(triangle);
//        System.out.println(result);
//    }

    public int minimumTotal(List<List<Integer>> triangle) {
        List<List<Integer>> dp = new ArrayList<>();
        int m = triangle.size();
        List<Integer> first = new ArrayList<>();
        first.add(triangle.get(0).get(0));
        dp.add(first);
        for (int i = 1; i < m; i++) {
            List<Integer> itemList = new ArrayList<>();
            List<Integer> row = triangle.get(i);
            int n = row.size();
            List<Integer> tmp = dp.get(i - 1);
            for (int j = 0; j < n; j++) {
                int leftVal = j - 1 >= 0 ? tmp.get(j - 1) : 100000;
                int rightVal = j < tmp.size() ? tmp.get(j) : 100000;
                int min = Math.min(leftVal, rightVal);
                itemList.add(min + row.get(j));
            }
            dp.add(itemList);
        }
        List<Integer> lastRow = dp.get(dp.size() - 1);
        int result = lastRow.get(0);
        for (int i = 1; i < lastRow.size(); i++) {
            if (lastRow.get(i) < result) {
                result = lastRow.get(i);
            }
        }
        return result;
    }
}
